
/*
 * Copyright (C) 2008-2009 Archie L. Cobbs. All rights reserved.
 *
 * $Id: GarbageCollection.java 377 2010-03-11 20:50:18Z archie.cobbs $
 */

package org.dellroad.sidekar.gc;

import java.lang.reflect.Array;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.dellroad.sidekar.ArrayField;
import org.dellroad.sidekar.AtomicField;
import org.dellroad.sidekar.CollectionField;
import org.dellroad.sidekar.Database;
import org.dellroad.sidekar.Entity;
import org.dellroad.sidekar.Field;
import org.dellroad.sidekar.FieldSwitchAdapter;
import org.dellroad.sidekar.ImplicitField;
import org.dellroad.sidekar.Item;
import org.dellroad.sidekar.MapField;
import org.dellroad.sidekar.ReferenceField;
import org.dellroad.sidekar.SimpleField;
import org.dellroad.sidekar.query.QueryIterable;
import org.dellroad.sidekar.query.QueryIterator;
import org.dellroad.sidekar.util.SidekarException;

/**
 * Contains the state associated with a single garbage collection run.
 */
class GarbageCollection {

    private final Database db;
    private final Marker marker;
    private final Set<Entity<?>> candidates;
    private final Recursor recursor = new Recursor();
    private final HashMap<Entity<?>, HashSet<Field<?>>> edges = new HashMap<Entity<?>, HashSet<Field<?>>>();
    private final Stack<Item<?>> stack = new Stack<Item<?>>();

    /**
     * Prepare for a new garbage collection.
     *
     * @throws SidekarException if no current transaction exists
     */
    public GarbageCollection(Database db, Marker marker, Set<Entity<?>> candidates) {

        // Initialize
        this.db = db;
        this.marker = marker;
        this.candidates = candidates;

        // Determine which fields in which entities can (indirectly) lead to a collection candidate
        Set<Entity<?>> sources = this.db.getEntities();
        while (true) {
            boolean changed = false;
            HashSet<Entity<?>> targets = new HashSet<Entity<?>>(this.edges.isEmpty() ? this.candidates : this.edges.keySet());
            for (Entity<?> src : sources) {
                for (Entity<?> target : targets) {
                    for (Field<?> field : src.getFields()) {
                        if (!field.canReference(target))
                            continue;
                        HashSet<Field<?>> refFields = this.edges.get(src);
                        if (refFields == null) {
                            refFields = new HashSet<Field<?>>();
                            this.edges.put(src, refFields);
                        }
                        if (!refFields.contains(field)) {
                            refFields.add(field);
                            changed = true;
                        }
                    }
                }
            }
            if (!changed)
                break;
        }
    }

    /**
     * Determine if instances of the given entity can possibly reference any potential garbage.
     * Note: this will include garbage entities as well (if they can reference themselves).
     */
    public boolean canReferenceCandidates(Entity<?> entity) {
        return this.edges.keySet().contains(entity);
    }

    /**
     * Determine if the given entity is candidate garbage.
     */
    public boolean isCandidate(Entity<?> entity) {
        return this.candidates.contains(entity);
    }

    /**
     * Mark reachable objects.
     *
     * @param roots root set of {@link Item}s
     */
    public void mark(List<QueryIterable<?>> rootIterables) {
        for (QueryIterable<?> iterable : rootIterables) {
            QueryIterator<?> i = iterable.iterator();
            while (i.hasNext()) {
                this.stack.push((Item<?>)i.next());
                this.processStack();
            }
            i.close();
        }
    }

    /**
     * Remove unreachable objects.
     *
     * @return number of items removed
     */
    public long sweep() {
        long count = 0;
        for (Entity<?> entity : this.candidates) {
            if (entity.isAbstract())
                continue;
            QueryIterator<?> i = entity.query(true).iterator();
            while (i.hasNext()) {
                Item<?> item = (Item<?>)i.next();
                if (this.marker.isMarked(item))
                    continue;
                i.remove();
                count++;
            }
            i.close();
        }
        return count;
    }

    /**
     * Process the stack of items to visit until it's empty.
     */
    private void processStack() {
        while (!this.stack.isEmpty()) {

            // Pop off next item
            Item<?> item = this.stack.pop();
            assert item != null;

            // Ignore detached items
            if (!item.isSidekarAttached())
                continue;

            // Have we already seen this item?
            if (this.marker.isMarked(item))
                continue;

            // Mark item as already seen
            this.marker.mark(item);

            // Scan fields for references
            HashSet<Field<?>> entityEdges = this.edges.get(item.getSidekarEntity());
            if (entityEdges == null)
                continue;
            for (Field<?> field : entityEdges) {
                Object value;
                if (field instanceof SimpleField)
                    value = ((SimpleField<?>)field).get(item);
                else
                    value = item;
                if (value != null) {
                    this.recursor.setValue(value);
                    field.visit(this.recursor);
                }
            }
        }
    }

    // Knows how to recurse on field values
    class Recursor extends FieldSwitchAdapter {

        private Object value;

        public void setValue(Object value) {
            this.value = value;
        }

        @Override
        protected <T> void caseImplicitField(ImplicitField<T> field) {
            throw new RuntimeException("internal error");
        }

        @Override
        protected <E> void caseAtomicField(AtomicField<E> field) {
            // do nothing
        }

        @Override
        public <E> void caseReferenceField(ReferenceField<E> field) {
            assert this.value != null;
            GarbageCollection.this.stack.push((Item<?>)this.value);
        }

        @Override
        public <E> void caseArrayField(ArrayField<E> field) {
            assert this.value != null;
            final Object array = this.value;
            final int length = Array.getLength(array);
            SimpleField<E> elemField = field.getElementField();
            for (int i = 0; i < length; i++) {
                this.value = Array.get(array, i);
                if (this.value != null)
                    elemField.visit(this);
            }
        }

        @Override
        protected <E> void caseCollectionField(CollectionField<E> field) {
            assert this.value != null;
            SimpleField<E> elemField = field.getElementField();
            QueryIterator<E> i = field.get((Item<?>)this.value).iterator();
            while (i.hasNext()) {
                E elem = i.next();
                if (elem != null) {
                    this.value = elem;
                    elemField.visit(this);
                }
            }
            i.close();
        }

        @Override
        public <K, V> void caseMapField(MapField<K, V> field) {
            assert this.value != null;
            SimpleField<K> keyField = field.getKeyField();
            SimpleField<V> valueField = field.getValueField();
            QueryIterator<Map.Entry<K, V>> i = field.get((Item<?>)this.value).entrySet().iterator();
            while (i.hasNext()) {
                Map.Entry<K, V> entry = i.next();
                K key = entry.getKey();
                if (key != null) {
                    this.value = key;
                    keyField.visit(this);
                }
                V val = entry.getValue();
                if (val != null) {
                    this.value = val;
                    valueField.visit(this);
                }
            }
            i.close();
        }

        @Override
        protected <T> void caseDefault(Field<T> field) {
            throw new RuntimeException("internal error");
        }
    }
}

